| 1. Identity statement | |
| Reference Type | Journal Article |
| Site | plutao.sid.inpe.br |
| Holder Code | isadg {BR SPINPE} ibi 8JMKD3MGPCW/3DT298S |
| Identifier | 8JMKD3MGP3W/3TEPCS5 |
| Repository | sid.inpe.br/plutao/2019/06.10.14.29 (restricted access) |
| Last Update | 2019:06.14.10.21.50 (UTC) lattes |
| Metadata Repository | sid.inpe.br/plutao/2019/06.10.14.29.01 |
| Metadata Last Update | 2020:01.06.11.35.23 (UTC) administrator |
| DOI | 10.1016/j.asoc.2019.105482 |
| ISSN | 1568-4946 |
| Label | lattes: 0096913881679975 3 ChagasLoreSant:2019:HyHeOv |
| Citation Key | ChagasLoreSant:2019:HyHeOv |
| Title | A hybrid heuristic for the overlapping cluster editing problem  |
| Year | 2019 |
| Access Date | 2024, May 19 |
| Type of Work | journal article |
| Secondary Type | PRE PI |
| Number of Files | 1 |
| Size | 806 KiB |
| 2. Context | |
| Author | 1 Chagas, Guilherme Oliveira 2 Lorena, Luiz Antonio Nogueira 3 Santos, Rafael Duarte Coelho dos |
| Resume Identifier | 1 2 8JMKD3MGP5W/3C9JHMQ 3 8JMKD3MGP5W/3C9JJ4N |
| Group | 1 LABAC-COCTE-INPE-MCTIC-GOV-BR 2 LABAC-COCTE-INPE-MCTIC-GOV-BR 3 LABAC-COCTE-INPE-MCTIC-GOV-BR |
| Affiliation | 1 Instituto Nacional de Pesquisas Espaciais (INPE) 2 Instituto Nacional de Pesquisas Espaciais (INPE) 3 Instituto Nacional de Pesquisas Espaciais (INPE) |
| Author e-Mail Address | 1 guilherme.chagas@inpe.br 2 3 rafael.santos@inpe.br |
| Journal | Applied Soft Computing |
| Volume | 81 |
| Pages | 105482 |
| Secondary Mark | A2_INTERDISCIPLINAR A2_ENGENHARIAS_IV A2_ENGENHARIAS_III A2_CIÊNCIA_DA_COMPUTAÇÃO B1_MATEMÁTICA_/_PROBABILIDADE_E_ESTATÍSTICA B1_ENGENHARIAS_II B1_BIOTECNOLOGIA |
| History (UTC) | 2019-06-10 14:29:01 :: lattes -> administrator :: 2019-06-10 14:43:22 :: administrator -> lattes :: 2019 2019-06-14 10:21:51 :: lattes -> administrator :: 2019 2020-01-06 11:35:23 :: administrator -> simone :: 2019 |
| 3. Content and structure | |
| Is the master or a copy? | is the master |
| Content Stage | completed |
| Transferable | 1 |
| Content Type | External Contribution |
| Version Type | publisher |
| Keywords | Overlapping cluster editing Cluster editing Overlapping clustering Hybrid heuristic |
| Abstract | Clustering problems are applicable to several areas of science. Approaches and algorithms are as varied as the applications. From a graph theory perspective, clustering can be generated by partitioning an input graph into a vertex-disjoint union of cliques (clusters) through addition and deletion of edges. Finding the minimum number of edges additions and deletions required to cluster data that can be represented as graphs is a well-known problem in combinatorial optimization, often referred to as cluster editing problem. However, many real-world clustering applications are characterized by overlapping clusters, that is, clusters that are non-disjoint. In these situations cluster editing cannot be applied to these problems. Literature concerning a relaxation of the cluster editing, where clusters can overlap, is scarce. In this work, we propose the overlapping cluster editing problem, a variation of the cluster editing where the goal is to partition a graph, also by editing edges, into maximal cliques that are not necessarily disjoint. In addition, we also present three slightly different versions of a hybrid heuristic to solve this problem. Each hybrid heuristic is based on coupling two metaheuristicsthat, together, generate a set of clusters; and one of three mixed-integer linear programming models, also introduced in this paper, that uses these clusters as input. The objective with the metaheuristics is to limit the solution exploration space in the models resolution, therefore reducing its computational time. Tests results show that the all proposed hybrid heuristic versions are able to generate good-quality overlapping cluster editing solutions. In particular, one version of the hybrid heuristic achieved, at a low computational cost, the best results in 51 of 112 randomly-generated graphs. Although the other two hybrid heuristic versions have harder to solve models, they obtained reasonable results in medium-sized randomly-generated graphs. In addition, the hybrid heuristic achieved good results identifying labeled overlapping clusters in a supervised data set experiment. Furthermore, we also show that, with our new problem definition, clustering a vertex in more than one cluster can reduce the edges editing cost. |
| Area | COMP |
| Arrangement | urlib.net > BDMCI > Fonds > Produção anterior à 2021 > LABAC > A hybrid heuristic... |
| doc Directory Content | access |
| source Directory Content | there are no files |
| agreement Directory Content | there are no files |
| 4. Conditions of access and use | |
| Language | en |
| Target File | 1-s2.0-S1568494619302522-main.pdf |
| User Group | lattes |
| Reader Group | administrator lattes |
| Visibility | shown |
| Archiving Policy | denypublisher denyfinaldraft24 |
| Read Permission | deny from all and allow from 150.163 |
| Update Permission | not transferred |
| 5. Allied materials | |
| Next Higher Units | 8JMKD3MGPCW/3ESGTTP |
| Citing Item List | sid.inpe.br/mtc-m21/2012/07.13.14.54.04 2 sid.inpe.br/mtc-m21/2012/07.13.14.58.32 1 sid.inpe.br/bibdigital/2013/09.22.23.14 1 |
| Dissemination | WEBSCI; PORTALCAPES; COMPENDEX. |
| Host Collection | dpi.inpe.br/plutao@80/2008/08.19.15.01 |
| 6. Notes | |
| Empty Fields | alternatejournal archivist callnumber copyholder copyright creatorhistory descriptionlevel e-mailaddress format isbn lineage mark mirrorrepository month nextedition notes number orcid parameterlist parentrepositories previousedition previouslowerunit progress project rightsholder schedulinginformation secondarydate secondarykey session shorttitle sponsor subject tertiarymark tertiarytype url |
| 7. Description control | |
| e-Mail (login) | simone |
| update | |